package main

import "fmt"

func main() {
	t3 := TreeNode{Val: 3}
	t5 := TreeNode{Val: 5}
	t7 := TreeNode{Val: 7}
	t2 := TreeNode{Val: 2, Left: &t3, Right: &t5}
	t9 := TreeNode{Val: 9, Right: &t7}
	t4 := TreeNode{Val: 4, Left: &t2, Right: &t9}
	fmt.Println(findTilt(&t4))
}

//给定一个二叉树，计算 整个树 的坡度 。
//
// 一个树的 节点的坡度 定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值 。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一
//样。空结点的坡度是 0 。
//
// 整个树 的坡度就是其所有节点的坡度之和。
//
//
//
// 示例 1：
//
//
//输入：root = [1,2,3]
//输出：1
//解释：
//节点 2 的坡度：|0-0| = 0（没有子节点）
//节点 3 的坡度：|0-0| = 0（没有子节点）
//节点 1 的坡度：|2-3| = 1（左子树就是左子节点，所以和是 2 ；右子树就是右子节点，所以和是 3 ）
//坡度总和：0 + 0 + 1 = 1
//
//
// 示例 2：
//
//
//输入：root = [4,2,9,3,5,null,7]
//输出：15
//解释：
//节点 3 的坡度：|0-0| = 0（没有子节点）
//节点 5 的坡度：|0-0| = 0（没有子节点）
//节点 7 的坡度：|0-0| = 0（没有子节点）
//节点 2 的坡度：|3-5| = 2（左子树就是左子节点，所以和是 3 ；右子树就是右子节点，所以和是 5 ）
//节点 9 的坡度：|0-7| = 7（没有左子树，所以和是 0 ；右子树正好是右子节点，所以和是 7 ）
//节点 4 的坡度：|(3+5+2)-(9+7)| = |10-16| = 6（左子树值为 3、5 和 2 ，和是 10 ；右子树值为 9 和 7 ，和是 1
//6 ）
//坡度总和：0 + 0 + 0 + 2 + 7 + 6 = 15
//
//
// 示例 3：
//
//
//输入：root = [21,7,14,1,1,2,2,3,3]
//输出：9
//
//
//
//
// 提示：
//
//
// 树中节点数目的范围在 [0, 10⁴] 内
// -1000 <= Node.val <= 1000
//
// Related Topics 树 深度优先搜索 二叉树 👍 213 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type TreeNode struct {
	Val int
	Left *TreeNode
	Right *TreeNode
}

func findTilt(root *TreeNode) int {
	var result int
	sum(root, &result)
	return result
}

func sum(root *TreeNode, result *int) int {
	if root == nil {
		return 0
	}
	leftSum := sum(root.Left, result)
	rightSum := sum(root.Right, result)
	*result += abs(leftSum, rightSum)
	return root.Val + leftSum + rightSum
}

func abs(a, b int) int {
	if a >= b {
		return a - b
	} else {
		return b - a
	}
}
//leetcode submit region end(Prohibit modification and deletion)
